package com.gyg.程序员面试金典;

import java.util.Arrays;

/**
 * 面试题 05.01. 插入
 * 解题思路：利用字符串拼接，
 * （1）将两个十进制数转换成二进制字符串
 * （2）根据给的i和j得到需要更换后的那部分字符串，
 * （3）将修改的字符串和不需要修改的字符串进行拼接，得到结果的二进制字符串
 * （4）将二进制字符串转换成十进制数
 */
public class T05_01 {
    public static void main(String[] args) {
        T05_01 test = new T05_01();
        /*int n = binaryToDecimalism(decimalismToBinary(178));
        System.out.println(n);*/
//        System.out.println(test.insertBits(1024, 19, 2, 6));
//        String s = "123456789";
//        System.out.println(s.substring(1,3));
        System.out.println(decimalismToBinary(23 << 2 << 1));
        System.out.println(decimalismToBinary(23 >> 2 >> 1));

    }


    /**
     * 位运算解法
     * 解题思路：
     * （1）通过右移获取到N左半部分
     * （2）通过左移来抛弃中间和右半部分，得到左半部分
     * （3）将M左移i位，正好得到中间部分
     * （4）将N和i位的1进行与运算，就能得到右半部分
     * （5）将left、middle、right三部分进行或运算（合并），得到最终的结果
     *
     * @return
     */
    public int insertBits2(int N, int M, int i, int j) {
//        （1）通过右移获取到N左半部分
        int left = N >> j >> 1;
//       （1）通过左移来抛弃中间和右半部分，得到左半部分
        left = left << j << 1;
//        （3）将M左移i位，正好得到中间部分
        int middle = M << i;
//        （4）将N和i位的1进行与运算，就能得到右半部分
        int right = N & ((1 << i) - 1);
//        （5）将left、middle、right三部分进行或运算（合并），得到最终的结果
//        假设left、middle、right的二进制长度都是N的二进制的长度，
//        可以看作left的右半部分全都是0，middle的左边右边部分都是0，right的左半部分都是0，
        return left | middle | right;
    }

    /**
     * 暴力解法
     *
     * @return
     */
    public int insertBits(int N, int M, int i, int j) {

//        （1）将两个十进制数转换成二进制字符串
        String nStr = decimalismToBinary(N);    // N的二进制字符串
        String mStr = decimalismToBinary(M);    // M的二进制字符串


//        （2）根据给的i和j得到需要更换后的那部分字符串，
        String removeStr = "";      //存储修改后的那一段字符串
        int rLen = j - i + 1;   //得到中间可以替换的长度
        String ss = "";         //暂时存放修改的那一段字符串中需要补充的0
        for (int k = 0; k < rLen - mStr.length(); k++) {
            ss += "0";
        }
//        得到最终的修改的那段字符串
        removeStr = ss + mStr;


//        （3）将修改的字符串和不需要修改的字符串进行拼接，得到结果的二进制字符串
        String resultStr = "";      //存在最终答案的二进制字符串
//        判断如果j是已经超出了N的长度，就合并removeStr和N的末尾部分
        if (j + 1 >= nStr.length()) {
            resultStr = removeStr + nStr.substring(nStr.length() - i, nStr.length());
        } else {
            //        判断如果j是没有N的长度，就合并N的第一段 + removeStr + N的末尾部分
            resultStr = nStr.substring(0, nStr.length() - j - 1) + removeStr + nStr.substring(nStr.length() - i, nStr.length());
        }

//        （4）将二进制字符串转换成十进制数
        return binaryToDecimalism(resultStr);
    }

    /**
     * 将一个十进制数变成二进制字符串
     *
     * @return
     */
    public static String decimalismToBinary(int num) {
        if (num == 0) {
            return "0";
        }
        String binaryNum = "";
        while (num != 0) {
            int remainder = num % 2;
            binaryNum = remainder + binaryNum;
            num /= 2;
        }
        return binaryNum;
    }

    /**
     * 将二进制字符串变成十进制整数
     *
     * @return
     */
    public static int binaryToDecimalism(String binaryStr) {
        int num = 0;
        char[] binaryArr = binaryStr.toCharArray();
        for (int i = 0; i < binaryArr.length; i++) {
            int cInt = Integer.parseInt(String.valueOf(binaryArr[i]));
            int cNum = cInt * (int) Math.pow(2, binaryArr.length - i - 1);
            num += cNum;
        }

        return num;
    }

}
